import java.io.*;
import java.util.Arrays;
import java.util.TreeSet;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.ArrayList;
import java.util.Random;

/**
 *
 * @author Zuzka Krejcova
 */
public class Gramatika
{
    protected TreeSet<String> neterminaly;
    protected TreeSet<String> terminaly;
    protected String koren;
    protected TreeMap<String,HashSet<ArrayList<String>>> pravidla;//[eps] reprezentuje znak epsilon
    protected boolean bezEpsilon = false;
    protected boolean bezNepouzitelnych = false;
    protected boolean bezJednoduchych = false;

    /**
     * Konstruktor gramatiky, pouziva uz hotove cleny ctverice
     * @param neterminaly
     * @param terminaly
     * @param koren
     * @param pravidla
     */
    public Gramatika(TreeSet<String> neterminaly, TreeSet<String> terminaly, String koren, TreeMap<String,HashSet<ArrayList<String>>> pravidla)
    {
        this.neterminaly = new TreeSet(neterminaly);
        this.terminaly = new TreeSet(terminaly); //kontrolovat, ze neterminaly neobsahuji terminaly a opacne
        this.koren = koren;
        this.pravidla = new TreeMap(pravidla);
    }

    /**
     * Konstruktor gramatiky, gramatika se cte a parsuje ze zadaneho vstupu
     * @param vstup
     * @throws Exception
     */
    public Gramatika(BufferedReader vstup) throws Exception
    {
        String vzor = "\\(\\{[^\\n\\}]+\\},\\{[^\\n\\}]*\\},[^\\n\\}]+,[^\\n\\}]+\\)";
        String vstupniString = vstup.readLine();
        String[] stringy1;
        neterminaly = new TreeSet();
        terminaly = new TreeSet();
        pravidla = new TreeMap();

        if (!vstupniString.matches(vzor)) throw new Exception("Hlavička gramatiky nevyhovuje vzoru.");
        stringy1 = vstupniString.split("},"); // "({netermy","{termy","koren,P)"
        stringy1[0] = stringy1[0].substring(2); // "neterm,neterm,.."
        stringy1[1] = stringy1[1].substring(1); // "term,term,.."
        neterminaly = parseSymboly(stringy1[0]);
        terminaly = parseSymboly(stringy1[1]);
        koren = stringy1[2].split(",")[0];
        zkontrolujSymboly();
        zkontrolujKoren();
        vstupniString = vstup.readLine(); // P:\n
        pravidla = parsePravidla(vstup,neterminaly, terminaly);
    }

    protected static TreeSet<String> parseSymboly(String vstup) // jenom symboly oddelene carkama
    {
        TreeSet<String> ret = new TreeSet();
        String[] stringy;
        stringy = vstup.split(",[\\s]*");
        ret.addAll(Arrays.asList(stringy));
        return ret;
    }

    protected static TreeMap<String,HashSet<ArrayList<String>>> parsePravidla
            (BufferedReader vstup, TreeSet<String> neterminaly, TreeSet<String> terminaly) throws Exception
    {
        TreeMap<String,HashSet<ArrayList<String>>> ret = new TreeMap();
        String[] stringy1, stringy2;
        String vstupniString = vstup.readLine(); // prvni radek pravidel
        int pocitadlo = 0;
        while (vstupniString != null) //cteni jednotlivych radku pravidel
        {
            pocitadlo++;
            HashSet<ArrayList<String>> pravidlo = new HashSet();
            ArrayList<String> derivace;
            stringy1 = vstupniString.split(" --> ");
            if ((stringy1.length < 2) || !neterminaly.contains(stringy1[0]))
                throw new Exception("Špatný tvar pravidla na "+pocitadlo+". řádku pravidel.");
            stringy2 = stringy1[1].split(" \\| ");
            stringy2[stringy2.length-1].trim();
            if (stringy2[stringy2.length-1].isEmpty())
                stringy2[stringy2.length-1]=" ";
            for (int i=0;i<stringy2.length;i++)
            {
                derivace = new ArrayList();
                if (!(stringy2[i].equals("[eps]") || stringy2[i].equals("\u03B5")))
                {
                    for (int j=0; j<stringy2[i].length();j++)
                    {//umi jen po znacich, treba dodelat cely string
                        if (!neterminaly.contains(stringy2[i].substring(j,j+1))
                           && !terminaly.contains(stringy2[i].substring(j,j+1)))
                               throw new Exception("Použitý symbol nepatří do gramatiky. "+
                               "Pravidla řádek "+pocitadlo+", "+(i+1)+". slovo, "+(j+1)+". znak.");
                        derivace.add(stringy2[i].substring(j,j+1));
                    }
                } else
                {
                    derivace.add("\u03B5");
                }
                pravidlo.add(derivace);
            }
            if (ret.containsKey(stringy1[0])) {
                ret.get(stringy1[0]).addAll(pravidlo);
            } else {
                ret.put(stringy1[0], pravidlo);
            }
            vstupniString = vstup.readLine();
        }
        return ret;
    }

    private void zkontrolujSymboly() throws Exception {
        for (String term : terminaly)
            if (neterminaly.contains(term)) throw new Exception("Symbol "+term+
            " se vyskytuje v neterminálech i terminálech. Dál gramatiku nenačítám.");
    }

    private void zkontrolujKoren() throws Exception {
        if (!neterminaly.contains(koren)) throw new Exception("Kořen není z množiny neterminálů.");
    }

    /**
     * Konstruktor gramatiky, vytvori nahodnou gramatiku podle zadanych kriterii
     * - rozsahu poctu netermu, termu a pravidel
     * @param netermyMin
     * @param netermyMax
     * @param termyMin
     * @param termyMax
     * @param pravidlaRadkyMin
     * @param pravidlaRadkyMax
     * @param pravidlaRetezceMin
     * @param pravidlaRetezceMax
     */
    public Gramatika(short netermyMin, short netermyMax, short termyMin,
                     short termyMax, short pravidlaRadkyMin, short pravidlaRadkyMax,
                     short pravidlaRetezceMin, short pravidlaRetezceMax)
    {
        Random generatorCisel = new Random();
        neterminaly = nahodneSymboly(netermyMin, netermyMax, false, generatorCisel);
        terminaly = nahodneSymboly(termyMin, termyMax, true, generatorCisel);
        int i = generatorCisel.nextInt(neterminaly.size());
        koren = (String)neterminaly.toArray()[i];
        pravidla = nahodnaPravidla(pravidlaRadkyMin, pravidlaRadkyMax, pravidlaRetezceMin, 
                                   pravidlaRetezceMax, koren, generatorCisel, neterminaly, terminaly);
    }

    protected static TreeSet<String> nahodneSymboly(short min, short max, boolean lowerCase, Random generatorCisel)
    {
        TreeSet<String> ret = new TreeSet();
        int i = generatorCisel.nextInt(max-min+1)+min; //kolik symbolu
        while (ret.size() < i)
        {
            int j = generatorCisel.nextInt(26);
            j += lowerCase?97:65;
            String s = ""+(char)j;
            ret.add(s);
        }
        return ret;
    }

    protected static TreeMap<String,HashSet<ArrayList<String>>> nahodnaPravidla
            (short radkyMin, short radkyMax, short retezceMin, short retezceMax,
             String koren, Random generatorCisel, TreeSet<String> neterminaly, TreeSet<String> terminaly)
    {
        TreeMap<String,HashSet<ArrayList<String>>> ret = new TreeMap();
        String[] netermy = new String[neterminaly.size()];
        String[] symboly = new String[neterminaly.size()+terminaly.size()];
        int j = 0;
        for (String neterm : neterminaly)
        {
            netermy[j] = neterm;
            symboly[j] = neterm;
            j++;
        }
        for (String term : terminaly)
        {
            symboly[j] = term;
            j++;
        }
        int i = generatorCisel.nextInt(radkyMax-radkyMin+1)+radkyMin; //kolik radku pravidel
        String neterm = koren;
        ret.put(neterm, new HashSet()); //pridej koren s prazdnym pravidlem
        ret.get(neterm).addAll(nahodnePravidlo(symboly, generatorCisel.nextInt(retezceMax-retezceMin+1)+retezceMin, generatorCisel));
        while (ret.size()<i) //dokud neni dost radku
        {
            neterm = netermy[generatorCisel.nextInt(netermy.length)]; //nahodne vyber neterm
            if (!ret.keySet().contains(neterm)) //zkontroluj, jestli jeste nebyl pouzit
            {
                ret.put(neterm, new HashSet()); //pridej ho s prazdnym pravidlem
                ret.get(neterm).addAll(nahodnePravidlo(symboly, generatorCisel.nextInt(retezceMax-retezceMin+1)+retezceMin, generatorCisel));
            }
        }
        return ret;
    }

    protected static HashSet<ArrayList<String>> nahodnePravidlo(String[] symboly, int retezcu, Random generatorCisel)
    {
        HashSet<ArrayList<String>> ret = new HashSet();
        ArrayList<String> slovo;
        while (ret.size() < retezcu) //dokud neni dost retezcu
        {
            slovo = new ArrayList();
            if ((ret.size() == (retezcu-1)) && generatorCisel.nextBoolean()) //je-li to posledni retezec, rozhodni zda epsilon
            {
                slovo.add("\u03B5"); //pridej epsilon
            } else //jinak vytvor nove slovo
            {
                int delka = generatorCisel.nextInt(4)+1; //zvol delku retezce 1-5
                while (slovo.size() < delka) //dokud neni retezec cely, pridavej libovolne symboly
                {
                    slovo.add(symboly[generatorCisel.nextInt(symboly.length)]);
                }
            }
            ret.add(slovo); //pridej slovo
        }
        return ret;
    }

    @Override
    public String toString()
    {
        String ret="";
        ret += "({";
            for (String neterm : neterminaly)
            {
                ret += neterm;
                if (!neterminaly.last().equals(neterm)) ret+=",";
            }
        ret += "},{";
            for (String term : terminaly)
            {
                ret += term;
                if (!terminaly.last().equals(term)) ret+=",";
            }
        ret += "},"+koren;
        ret += ",P)\nP:\n";
            for (String neterm : pravidla.keySet())
            {
                boolean eps = false;
                boolean posledni = false;
                boolean vynechat = false;
                ret += neterm+" --> ";
                int i = 1;
                for (ArrayList<String> pravidlo : pravidla.get(neterm))
                {
                    for (String symbol : pravidlo)
                    {
                        if (symbol.equals("[eps]") || symbol.equals("\u03B5"))
                        {
                            eps = true;
                            if (pravidla.get(neterm).size()==i) posledni = true;
                            vynechat = true;
                        } else
                        {
                            ret+=symbol;
                        }
                    }
                    if ((pravidla.get(neterm).size()>i)&&!vynechat) ret+=" | ";
                    vynechat = false;
                    i++;
                }
                if ((eps)&&(!posledni)) ret += " | ";
                if (eps) ret += "\u03B5";
                ret+="\n";
            }
            return ret;
    }
}
